`
https://leetcode.cn/problems/unique-binary-search-trees/
`

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function (n) {
  // 备忘录的值初始化为 0
  let memo = new Array(n + 1).fill(null).map(() => new Array(n + 1).fill(0));

  // 定义：计算闭区间 [lo, hi] 组成的 BST 个数
  const count = (lo, hi) => {
    // 对应空结点 null，空结点也是一种情况
    if (lo > hi)  {
      return 1;
    }
    // 查备忘录
    if (memo[lo][hi] !== 0) {
      return memo[lo][hi];
    }

    let res = 0;
    // 遍历区间 [lo, hi] 中的每个节点 i，将其作为根节点
    for (let i = lo; i <= hi; i++) {
      // 左子树由区间 [lo, i-1] 组成
      const left = count(lo, i - 1);
      // 右子树由区间 [i+1, hi] 组成
      const right = count(i + 1, hi);
      // 并将它们的乘积累加到 res 中
      res += left * right;
    }
    // 将结果存入备忘录
    memo[lo][hi] = res;

    return res;
  }
  return count(1, n);
};

console.log(numTrees(5))